package dyyx;

import java.util.*;

public class BinaryTreeTravel {

	public static void main(String[] args) throws Exception {

		Node node1 = new Node(1);

		Node node2 = new Node(2);
		Node node3 = new Node(3);

		Node node4 = new Node(4);
		Node node5 = new Node(5);

		Node node6 = new Node(6);
		Node node7 = new Node(7);

		node1.left = node2;
		node1.right = node3;

		node2.left = node4;
		node2.right = node5;

		node3.left = node6;
		node3.right = node7;

		System.out.println("levelTraversalUseArrayDeque");
		levelTraversalUseArrayDeque(node1);
		System.out.println();

		System.out.println("levelTraversalUseLinkedList");
		levelTraversalUseLinkedList(node1);
		System.out.println();

		System.out.println("depthTraversalNonRecursion");
		depthTraversalNonRecursion(node1);
		System.out.println();

		System.out.println("preOrderTraverse1");
		preOrderTraverse1(node1);
		System.out.println();

		System.out.println("midOrderTraverse1");
		midOrderTraverse1(node1);
		System.out.println();

		System.out.println("postOrderTraverse1");
		postOrderTraverse1(node1);
		System.out.println();

	}

	public static void preOrderTraverse1(Node root) {
		if (root == null) {
			return;
		}
		System.out.print(root.value + " ");
		preOrderTraverse1(root.left);
		preOrderTraverse1(root.right);
	}

	public static void midOrderTraverse1(Node root) {
		if (root == null) {
			return;
		}
		midOrderTraverse1(root.left);
		System.out.print(root.value + " ");
		midOrderTraverse1(root.right);
	}

	public static void postOrderTraverse1(Node root) {
		if (root == null) {
			return;
		}
		postOrderTraverse1(root.left);
		postOrderTraverse1(root.right);
		System.out.print(root.value + " ");
	}

	public static void levelTraversalUseArrayDeque(Node node) {
		if (node == null) {
			return;
		}
		ArrayDeque<Node> deque = new ArrayDeque<Node>();
		// add addLast
		deque.add(node);

		while (!deque.isEmpty()) {
			// remove removeFirst
			Node rnode = deque.remove();
			System.out.print(rnode.value + " ");

			if (rnode.left != null) {
				deque.add(rnode.left);
			}
			if (rnode.right != null) {
				deque.add(rnode.right);
			}
		}
	}

	public static void levelTraversalUseLinkedList(Node root) {
		if (root == null) {
			return;
		}
		LinkedList<Node> queue = new LinkedList<>();
		// offer add linkLast
		// queue.offer(root);

		queue.add(root);

		while (!queue.isEmpty()) {
			// poll unlinkFirst
			// Node node = queue.poll();
			// remove removeFirst unlinkFirst
			Node node = queue.remove();
			System.out.print(node.value + " ");
			if (node.left != null) {
				queue.offer(node.left);
			}
			if (node.right != null) {
				queue.offer(node.right);
			}
		}
	}

	public static void depthTraversalNonRecursion(Node node) {
		if (node == null) {
			return;
		}
		Stack<Node> stack = new Stack<Node>();
		stack.push(node);
		while (!stack.isEmpty()) {
			Node rnode = stack.pop();
			System.out.print(rnode.value + " ");
			if (rnode.right != null) {
				stack.push(rnode.right);
			}
			if (rnode.left != null) {
				stack.push(rnode.left);
			}
		}
	}

}
